Polynomial evaluation
$$ \frac{p_0 + p_1 ⋅ x + p_2 ⋅ x^2 + p_3 ⋅ x^3 + p_4 ⋅ x^4 + p_5 ⋅ x^5} {q_0 + q_1 ⋅ x + q_2 ⋅ x^2 + q_3 ⋅ x^3 + q_4 ⋅ x^4 + q_5 ⋅ x^5 + x^6} $$
Basic algorithms
Horners rule
For Monomial basis
p = p5
p = p * x + p4
p = p * x + p3
p = p * x + p2
p = p * x + p1
p = p * x + p0
q = x + q5
q = q * x + q4
q = q * x + q3
q = q * x + q2
q = q * x + q1
q = q * x + q0
r = p / q
Clenshaw algorithm
Generalization, specifically for Chebyshev basis.
https://en.wikipedia.org/wiki/Clenshaw_algorithm
De Castlejau's algorithm
For Bernstein basis
https://en.wikipedia.org/wiki/De_Casteljau%27s_algorithm
https://en.wikipedia.org/wiki/De_Boor%27s_algorithm
Easy polynomials
https://en.wikipedia.org/wiki/Arithmetic_circuit_complexity
https://en.wikipedia.org/wiki/Exponentiation_by_squaring
https://en.wikipedia.org/wiki/Addition-chain_exponentiation
https://en.wikipedia.org/wiki/Vectorial_addition_chain
WNAF, Pippenger's algorithm, etc.
Preprocessing
$$ y = p_0 + p_1 ⋅ x + p_2 ⋅ x^2 + p_3 ⋅ x^3 + x^4 $$
would take three multiplications to evaluate
p = x + p3
p = p * x + p2
p = p * x + p1
p = p * x + p0
but can also be evaluated using only two by
$$ \begin{aligned} a &= (x + β_0) ⋅ x + β_1 & y &= (a + β_2) ⋅ a + β_3 \end{aligned} $$
with
$$ \begin{aligned} β_0 &= \frac12\p{a_3 - 1} & z &= a_2 - β_0 ⋅ \p{β_0 + 1} & β_1 &= a_1 - β_0 ⋅ z \\ β_2 &= z - 2 ⋅ β_1 & β_3 &= a_0 - β_1 ⋅ \p{β_1 + β_2} \end{aligned} $$
a = x + β0
a = a ⋅ x + β1
y = a + β2
y = y ⋅ a + β3
Pan's scheme for one polynomial
See §3.3 of the Pan's 1966 paper.
Assuming p monic
g2 = x * x
h2 = g2 + x
p1 = x + l1
g4_1 = (g2 + l3) * (h2 + l2) + l4
p5 = p1 * g4_1 + l5
g4_2 = (g2 + l7) * (h2 + l6) + l8
p9 = p5 * g4_2 + l9
# Output formulas
p1 = p1
p2 = p1 * x + a0
p3 = p1 * (g2 + a0) + a1
p4 = (p1 * (g2 + a0) + a1) * x + a2
p5 = p5
p6 = p5 * x + a0
p7 = p5 * (g2 + a0) + a1
p8 = (p5 * (g2 + a0) + a1) * x + a2
p9 = p9
p10 = p9 * x + a0
p11 = p9 * (g2 + a0) + a1
p12 = (p9 * (g2 + a0) + a1) * x + a2
(6,7)-term rat scheme: 4 + 5 muls.
p5 & p6
g2 = x * x
h2 = g2 + x
p1 = x + l1
g4_1 = (g2 + l3) * (h2 + l2) + l4
p5 = p1 * g4_1 + l5
p1 = x + l1
g4_1 = (g2 + l3) * (h2 + l2) + l4
p5 = p1 * g4_1 + l5
p6 = p5 * x + a0
above: 1 + 2 + 3 = 6 muls.
knuth explicits: 3 + 3 = 6 muls
$$ p(x) = p_0 + p_1 ⋅ x + p_2 ⋅ x^2 + p_3 ⋅ x^3 + p_4 ⋅ x^4 + x^5 $$
$$ q(x) = q_0 + q_1 ⋅ x + q_2 ⋅ x^2 + q_3 ⋅ x^3 + q_4 ⋅ x^4 + q_5 ⋅ x^5 + x^6 $$
Paterson-Stockmeyer
Consider the $n$-term monic polynomial where $n = 2 ⋅ k$
$$ p(x) = p_0 + p_1 ⋅ x + p_2 ⋅ x^2 + \cdots + p_{n-2} ⋅ x^{n-2} + x^{n-1} $$
We can rewrite it using two $k$-term monic polynomial $p_1$ and $p_2$:
$$ p(x) = p_1(x) + (x^k + a) ⋅ p_2(x) $$
Where $a = p_{k-1} -1$ and $p_2$ the top half of $p$ and $p_1$ is the lower half of $p$ with $a ⋅ p_2$ subtracted.
$x^2 = x ⋅ x$
$x^4 = x^2 ⋅ x^2$
$p(x) = p_0(x) + (x^4 + a_0) ⋅ p_1(x)$ with $p_0 = c_0 + c_1 ⋅ x + c_2 ⋅ x^2 + c_3 ⋅ x^3$
$p_0(x) = p_2(x) + (x^2 + a_0) ⋅ p_3(x)$
Random
Schwartz–Zippel lemma
https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma
Vieta's formula
https://en.wikipedia.org/wiki/Vieta%27s_formulas
Frobenius Endomorphism
https://en.wikipedia.org/wiki/Frobenius_endomorphism
Abert method
https://en.wikipedia.org/wiki/Durand%E2%80%93Kerner_method
https://en.wikipedia.org/wiki/Aberth_method
Reference
https://en.wikipedia.org/wiki/Arithmetic_circuit_complexity
- V.Ya. Pan (1966). "Methods of Computing Values of Polynomials" doi
- S. Winograd (1970). "On the number of multiplications necessary to compute certain functions" doi
- M.O. Rabin & S. Winograd (1972). "Fast Evaluation of Polynomials by Rational Preparation" doi
- D. Knuth (2011). "The Art of Computer Programming – Volume 2: Seminumerical Algorithms" isbn
http://eprints.maths.manchester.ac.uk/2700/3/fasi19.pdf
